package com.future;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Description:
 *给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subsets-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author weiruibai.vendor
 * Date: 2022/2/23 00:08
 */
public class Solution_subsetsWithDup_90 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 2};
        subsetsWithDup(nums);
    }

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Model model = new Model(nums);
        List<List<Integer>> ans = model.getAns();
        Set<List<Integer>> set= new HashSet<>(ans);
        return set.stream().collect(Collectors.toList());
    }


    static class Model {

        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        int length;

        public Model(int[] nums) {
            if (null == nums) {
                return;
            }
            this.length = nums.length;
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
            }
            process(new ArrayList<>(), 0);
        }

        public List<List<Integer>> getAns() {
            return ans;
        }

        private void process(List<Integer> paths, int curIndex) {
            if (curIndex == length) {
                ArrayList<Integer> integers = new ArrayList<>(paths);
                integers.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1-o2;
                    }
                });
                ans.add(integers);
                return;
            }
            process(paths, curIndex + 1);
            Integer value = list.get(curIndex);
            paths.add(value);
            process(paths, curIndex + 1);
            paths.remove(paths.size() - 1);
        }
    }
}
